from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return -1

        s, e = 0, len(nums)
        while s < e:
            if e - s == 1:
                if nums[s] == target:
                    return s
                else:
                    return -1

            mid = (e-s) // 2 + s
            midv = nums[mid]
            first, last = nums[s], nums[e - 1]
            rotated = first > last # 不存在重复的元素

            if target == midv:
                return mid
            elif target == last:
                return e - 1
            elif target == first:
                return s
            else:
                if rotated:
                    leftRotated = first > midv
                    if leftRotated:
                        if midv < target and target < last:
                            s = mid + 1
                            e = e - 1
                        else:
                            s = s + 1
                            e = mid
                    else:
                        if first < target and target < midv:
                            s = s + 1
                            e = mid
                        else:
                            s = mid + 1
                            e = e - 1
                else:
                    if target < midv:
                        s = s + 1
                        e = mid
                    else:
                        e = e - 1
                        s = mid + 1
        return -1
solu = Solution()
print(solu.search([4,5,6,7,0,1,2], 5) == 1)
print(solu.search([4,5,6,7,0,1,2], 0) == 4)
print(solu.search([1, 3], 0) == -1)
print(solu.search([1, 3], 3) == 1)
print(solu.search([7,8,1,2,3,4,5,6], 2) == 3)
